//
// Created by 高森森 on 2022/2/10.
//

#ifndef LEETCODE_SOLUTION29_H
#define LEETCODE_SOLUTION29_H
#include<iostream>
#include<vector>
using namespace std;

class Solution29 {
public:
    vector<int>res;
    vector<vector<int>>hash;
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        vector<vector<pair<int,char>>>graph(n);
        for(int i=0;i<n-1;i++){
            graph[edges[i][0]].push_back(make_pair(edges[i][1],labels[edges[i][1]]));
            graph[edges[i][1]].push_back(make_pair(edges[i][0],labels[edges[i][0]]));
        }
        res=vector<int>(n);
        hash=vector<vector<int>>(n,vector<int>(26,0));
       vector<bool>visited(n,0);
        dfs(0,graph,labels,visited);
       return res;
    }

    void dfs(int index,vector<vector<pair<int,char>>>&graph, string &lables,vector<bool>&visited) {
        visited[index]=1;
        hash[index][lables[index]-'a']++;
        for(auto neigh:graph[index]){
            if(visited[neigh.first])
                continue;
            dfs(neigh.first,graph,lables,visited);
            for(int i=0;i<26;i++)
                hash[index][i]+=hash[neigh.first][i];
        }
        res[index]=hash[index][lables[index]-'a'];
    }
};


#endif //LEETCODE_SOLUTION29_H
